package com.yun.algorithmproblem.leetcode;

/**
 * 6. Z 字形变换
 * <p>
 * 将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。
 * <p>
 * 比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：
 * <p>
 * P   A   H   N
 * A P L S I I G
 * Y   I   R
 * 之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。
 * <p>
 * 请你实现这个将字符串进行指定行数变换的函数：
 * <p>
 * string convert(string s, int numRows);
 */
public class Leetcode6 {

    public static void main(String[] args) {
        Leetcode6 obj = new Leetcode6();
        String a = obj.convert("PAYPALISHIRING", 5);
        System.out.println(a);
    }
    /**
     * rows=4
     * 第一排 0 6 12
     * 第二排 1 5 7 11 13
     * 第三排 2 4 6 8
     *
     * rows=5
     * P       H      0 8 16 差8 差8
     * A     S I      1 7 9 15 17 差6 差2 差6 差2
     * Y   I   R      2 6 10 14 18 差4 差4 差4 差4
     * P L     I G    3 5 11 13 19 差2 差6 差2 差6
     * A       N
     */

    public String convert(String s, int numRows) {
        if (numRows == 1) {
            return s;
        }
        char[] chars = s.toCharArray();
        StringBuilder sb = new StringBuilder();
        int length = chars.length;
        int upGap = (numRows << 1) - 2;
        int downGap = 0;
        for (int i = 0; i < numRows; i++) {
            int index = i;
            boolean up = true;
            while (index < length) {
                if (up) {
                    if (upGap != 0) {
                        sb.append(chars[index]);
                        index += upGap;
                    }
                    up = false;
                } else {
                    if (downGap != 0) {
                        sb.append(chars[index]);
                        index += downGap;
                    }
                    up = true;
                }
            }
            upGap -= 2;
            downGap += 2;
        }
        return sb.toString();
    }
}
